It is frequently necessary to navigate through a large inverted index of database items to identify a small number of entries that meet very specific criteria. For instance, a user searching a database of used cars may wish to quickly winnow a search down to a red Toyota costing no more than $10,000, manufactured in 1995 or later, located within fifty miles of San Francisco, and with a text description containing the words “excellent condition”.
A text query such as “excellent condition” may be handled using standard methods in information retrieval. A query, such as, “red Toyota costing no more than $10,000, manufactured in 1995 or later, located within fifty miles of San Francisco” is known as a range query. Range queries are traditionally handled using one of two techniques. First, computational geometry may be used. Computational geometry is feasible provided that the attributes (e.g., price, age) are numerical values that can be ordered. Computational geometry is not available for non-orderable attributes, known as categorical attributes, such as color. A second approach to handling range queries is through a relational database. Relational databases provide the ability to answer a very rich set of queries, expressed in the Structured Query Language (SQL). In addition, relational databases provide transaction logging and recovery. This richness of functionality comes at the price of relatively slow execution speeds. To process a search, the parameters within the search query must be converted to an SQL statement. The SQL statement must then be applied to the database. While it is possible to articulate parametric queries as SQL statements, this approach is time consuming since parameters must be converted to SQL and then be applied to the database. In high-volume electronic commerce and marketplace applications, such as those commonly found on the Internet, it is not feasible to rely on a database to react in real time when hundreds of users are concurrently launching searches, each of which involves several fields or parameters.
In view of the foregoing, it would be highly desirable to provide improved techniques for processing search queries. More particularly, it would be highly desirable to provide an improved technique for processing queries that include multiple fields or parameters.